#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,Q,k,a[3000006],b[3000006],ans;
struct node{
	int id,s;
}g[100005];
void dfs(int x){
	if(x>Q){
		for(int i=1;i<=n;i++) b[i]=0;
		for(int i=1;i<=Q;i++) b[g[i].id]=g[i].s;
		for(int i=1;i+m-1<=n;i++){
			int opt=0;
			for(int j=i,l=1;j<=i+m-1;j++,l++)
				if(b[j]!=a[l]) {opt=1;break;}
			if(opt==0) ans++;
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		g[x].id=i;
		for(int j=1;j<=k;j++){
			g[x].s=j;
			dfs(x+1);
			g[x].s=0;
		}
		g[x].id=0;
	}
}
signed main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>Q>>k;
	for(int i=1;i<=m;i++) cin>>a[i];
	if(Q<m) {cout<<0;return 0;}
	dfs(1);
	cout<<ans;
	return 0;
}